As the information age has rapidly progressed, the relative contributions of different components defining our economies have also changed. For example, in our modern society, economic value creation is no longer created only by the fabrication of physical objects, but is created also within the context of information exchange. An essential initial part of the effort needed to fabricate physical objects lies in such creation of 3D model descriptions of the objects.
In the past, such 3D solid model descriptions had been presented with a fairly restrictive shape variety, e.g., 2D drawings such as blueprints. Today, these 3D solid objects and surfaces are typically described with computer-aided design (CAD) systems using digital data sets. Here, the richest shape variety can be described using free-form boundary surfaces that are typically defined by Non-Uniform Rational B-Spline (NURBS) surface patches.
Consequently, the most important and fundamental part of the value creation process for a 3D object consists in creating the digital 3D solid model bounded by free form surfaces. As this digital data model is an expensive and important part of the production process, there exists the natural need to protect the ownership of this data model.
Digital data models describing solid objects are often accessible to various parties. This occurs, for example, when the detailed design specifications are shown to prospective buyers of a physical copy of the solid object. Furthermore, the digital model data could be known to another party, e.g., a subcontractor or by industrial espionage, e.g., when data are communicated via the internet. It is also possible that a party could approximate digital model data by reconstructing the geometric model by reverse engineering a single physical prototype. In other instances, there could be a need for several engineers working together to simultaneously access a design database and to make changes in the database that are instantly accessible by others on the team. At the same time, there is a need for conveying these data to designers at remote locations while providing a high level of security on proprietary designs.
When proprietary digital content is exposed to the internet, it can become an easy target for malicious parties who wish to reproduce unauthorized copies. In addition, a model could be stolen or sized up for comparison direct from a file, or even by measuring and entering data points or by laser scanning a real solid.
For this reason, digital watermarking, a process in which special data, i.e., a “digital watermark,” is embedded into digital content to assist in identifying ownership of the content, has become an active research topic.
Digital watermarks can be classified by visibility, i.e., visible watermarks and invisible watermarks. A visible watermark involves embedding a watermark, which is recognizable by the user, into the proprietary digital content to prevent piracy by a third party. On the other hand, an invisible watermark is not recognizable by the user, unless it is extracted by a computer program.
Several studies on digital watermarking techniques for 3D polygonal models have been prompted by the increasing popularity of virtual reality modeling language (VRML) and the imminent standardization of MPEG-4 [19, 13, 23, 4, 25]. However, existing watermarking techniques, such as embedding data by slightly changing the control points, or placing a pattern into the mesh, are vulnerable to coordinate transformation, random noise and malicious action by a user.
Moreover, these techniques cannot be applied directly to computer-aided design (CAD) based objects, which are usually represented by Non-Uniform Rational B-Spline (NURBS) surfaces. NURBS representation provides the richest shape variety for objects bounded by free-form surfaces. Creation of such 3D models is an expensive and important part of the whole production process, and there exists the natural need to protect the ownership of this data model.
Review of Related Work
Digital Watermarking on 3D Polygonal Models
Watermarking on 3D polygonal models is useful for protecting Virtual Reality Modeling Language (VRML) models. Almost all methods are designed for triangle meshes, and embed information by perturbing vertex coordinates, or changing topological connectivity.
Ohbuchi et al. [19] proposed pioneer watermarking methods for both coordinates and connectivity. In one method, one or more bits of data are embedded in a triangle by slightly altering the ratio of two edges of the triangle or its angle. It is invariant to rigid transformation and uniform scaling. Watermark bits are sequentially embedded in triangles ordered according to spanning trees. A second method uses the ratio of tetrahedra volumes, which are invariant to affine transformation. Tetrahedra are defined by three vertices of a base triangle and a common apex vertex. Watermark information is embedded by altering the ratios of volumes using coordinate perturbation. In addition, Ohbuchi et al. proposed other methods that embed information by changing topological connectivity. One method embeds visible patterns on a surface by subdividing triangle meshes. Another method embeds 0/1 patterns by modifying the connectivity of triangle strips.
Yeo and Yeung [25] proposed a fragile watermarking method that detects unauthorized alterations of 3D models. In this method, vertex coordinates are slightly altered such that the hash function of each vertex coordinates matches another hash function applied to the center of its neighboring vertices. When a 3D model is altered without authorization, its watermark information is destroyed and alteration is detected.
Benedens [4] proposed a method that embeds information in surface normal distribution. In this method, surface normals are mapped on a unit sphere, and groups of similar normals are altered in order to embed watermarking information. This method resists mesh modification, such as polygonal simplification, if the original model has dense meshes.
Kanai et al. [13] proposed a spread-spectrum watermarking method for 3D polygonal models, by embedding watermark information in the frequency domain of 3D models. This method is based on wavelet transformations and multiresolution representations that represent a 3D model as a simple base mesh with wavelet coefficients on each level of detail. The watermark information is embedded in the large wavelet coefficient vectors at one or more resolution levels of detail. The robustness of the watermark can be controlled by the level in which watermark information is embedded. This method can resist affine transformation and polygonal simplification.
Praun et al. [23] enhanced approaches of Kanai et al [13] and Benedens [4]. They constructed scalar basis functions over the mesh vertices using multiresolution analysis, and perturbed vertex coordinates along the direction of the surface normal weighted by the basis functions. In addition, they proposed mesh optimization technique for detecting watermark information in attacked meshes.
Digital Watermarking on Constructive Solid Geometry (CSG) Models
Fornaro and Sanna [8] have developed a public watermarking technique for authentication of CSG models. They considered two places in which to embed the watermark, namely solids and comments. In order to store watermark within a solid, they defined a new kind of node linked to the original CSG tree. To keep the watermark invisible, they used null volume objects, e.g., a sphere with a null radius. However, this technique is fragile to malicious action of the user.
Digital Watermarking on 3D Non-Uniform Rational B-Spline (NURBS) Surfaces
NURBS surfaces are very popular in engineering CAD, but there are few watermarking methods for NURBS models.
Ohbuchi et al. [20] proposed a data embedding algorithm for NURBS curves and surfaces, which employed rational linear parameterization for encoding watermark information. Since this method uses redundancy of re-parameterization, it preserves the exact geometric shape of NURBS curves and surfaces. Their method is simple and useful, but such watermark information can be easily removed, for example via approximation, without degrading the quality of the surfaces.
Summary Critique of State-of-the-art Methods
The use of commercial 3D CAD systems and collaboration via the Internet are becoming very common in the engineering field. As a result, protection of proprietary CAD data has become an important issue. As described above, several methods have been proposed for watermarking 3D polygonal models, especially triangular meshes. Although their methods are useful for Virtual Reality Modeling Language (VRML) models, they are inadequate for engineering use, because 3D CAD models are commonly designed using free-form curves and surfaces.
We are aware of only one method that has been proposed for watermarking of NURBS surfaces, namely Ohbuchi et al. [20], discussed above.
Currently, no robust watermarking methods exist for NURBS surfaces. Thus, proprietary engineering 3D CAD data that, for example, are transferred via the Internet, cannot be effectively protected.
References
The following references, cited within the text, are incorporated by reference herein in their entireties.                [1] S. L. Abrams, L. Bardis, C. Chryssostomidis, N. M. Patrikalakis, S. T. Tuohy, F. -E. Wolter, and J. Zhou. The geometric modeling and interrogation system Praxiteles. Journal of Ship Production, 11(2):117-132, May 1995.        [2] S. L. Abrams, W. Cho, C. -Y. Hu, T. Maekawa, N. M. Patrikalakis, E. C. Sherbrooke, and X. Ye. Efficient and reliable methods for rounded-interval arithmetic. Computer-Aided Design, 30(8):657-665, July 1998.        [3] T. Asano, M. Edahiro, H. Imai, M. Iri, and K. Murota. Practical use of bucketing techniques in computational geometry. In G. T. Toussaint, editor, Computational Geometry, Machine Intelligence and Pattern Recognition Vol. 2, pages 153-195. North Holland, 1985.        [4] O. Benedens. Geometry-based watermarking of 3D models. IEEE Computer Graphics and Applications, 19(1):46-55, 1999.        [5] G. Borgefors. Distance transformations in arbitrary dimensions. Computer Vision, Graphics, and Image Processing, 27:321-345, 1984.        [6] T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. MIT Press, Cambridge, Mass., 1990.        [7] S. Crandall, D. Karnopp, E. Kurtz, and D. P. Brown. Dynamics of Mechanical and Electromechanical Systems. McGraw-Hill, 1968.        [8] C. Fornaro and A. Sanna. Public key watermarking for authentication of CSG models. Computer Aided Design, 32(12):727-735, 2000.        [9] D. Hilbert and S. Cohn-Vossen. Geometry and the Imagination. Chelsea, N.Y., 1952.        [10] C. -Y. Hu. Towards Robust Interval Solid Modeling for Curved Objects. PhD thesis, Massachusetts Institute of Technology, Cambridge, Mass., May 1995.        [11] C. Y. Hu, T. Maekawa, N. M. Patrikalakis, and X. Ye. Robust interval algorithm for surface intersections. Computer-Aided Design, 29(9):617-627, September 1997.        [12] C. Y. Hu, T. Maekawa, E. C. Sherbrooke, and N. M. Patrikalakis. Robust interval algorithm for curve intersections. Computer-Aided Design, 28(6/7):495-506, June/July 1996.        [13] S. Kanai, H. Date, and T. Kishinami. Digital watermarking for 3D polygons using multiresolution wavelet decomposition. In Proceedings of the Sixth IFIP WG 5. 2/GI International Workshop on Geometric Modelling: Fundamentals and Applications, Tokyo, December, 1998, pages 296-307, 1998.        [14] T. Maekawa. Robust Computational Methods for Shape Interrogation. PhD thesis, Massachusetts Institute of Technology, Cambridge, Mass., June 1993.        [15] T. Maekawa and N. M. Patrikalakis. Computation of singularities and intersections of offsets of planar curves. Computer Aided Geometric Design, 10(5):407-429, October 1993.        [16] T. Maekawa and N. M. Patrikalakis. Interrogation of differential geometry properties for design and manufacture. The Visual Computer, 10(4):216-237, March 1994.        [17] T. Maekawa, F. -E. Wolter, and N. M. Patrikalakis. Umbilics and lines of curvature for shape interrogation. Computer Aided Geometric Design, 13(2):133-161, March 1996.        [18] M. E. Mortenson. Geometric Modeling. John Wiley and Sons, New York, 1985.        [19] R. Ohbuchi, H. Masuda, and M. Aono. Watermarking three-dimensional polygonal models through geometric and topological modifications. IEEE Journal on Selected Areas in Communications, 16(14):551-560, May 1998.        [20] R. Ohbuchi, H. Masuda, and M. Aono. A shape-preserving data embedding algorithm for NURBS curves and surfaces. In Proceedings of Computer Graphics International, CGI '99, June 1999, pages 180-187. IEEE Computer Society, 1999.        [21] N. M. Patrikalakis and L. Bardis. Localization of rational B-spline surfaces. Engineering with Computers, 7(4):237-252, 1991.        [22] J. Pegna and F. -E. Wolter. Surface curve design by orthogonal projection of space curves onto free-form surfaces. Journal of Mechanical Design, ASME Transactions, 118(1):45-52, March 1996.        [23] E. Praun, H. Hoppe, and A. Finkelstein. Robust mesh watermarking. In Proceedings of SIGGRAPH '99, Los Angeles, Aug. 8-13, 1999, pages 49-56. ACM, 1999.        [24] E. C. Sherbrooke and N. M. Patrikalakis. Computation of the solutions of nonlinear polynomial systems. Computer Aided Geometric Design, 10(5):379-405, October 1993.        [25] B. L. Yeo and M. M. Yeung. Watermarking 3D objects for verification. IEEE Computer Graphics and Applications, 19(1):36-45, 1999.        [26] J. Zhou, E. C. Sherbrooke, and N. M. Patrikalakis. Computation of stationary points of distance functions. Engineering with Computers, 9(4):231-246, Winter 1993.        